847E - Packmen - CodeForces Solution


binary search dp *1800

Please click on ads to support us..

C++ Code:

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

int N;
string line;

bool ok(int mid) {
	int p = -1, a = -1;
	int pUsed = -1;
	for (int i = 0; i < N; i++) {
		if (line[i] == '*') {
			if (a == -1) {
				if (p != -1) {
					bool cover;
					if (pUsed > 0) {
						int pToUse = i - p;
						int minUse = min(pUsed, pToUse);
						int maxUse = max(pUsed, pToUse);
						if (2*minUse+maxUse <= mid) cover = true;
						else cover = false;
					} else {
						cover = (i-p <= mid);
					}
					if (!cover) {
						p = -1;
						pUsed = -1;
						a = i;
					}
				} else {
					a = i;
				}
			}
		} else if (line[i] == 'P') {
			if (p == -1) {
				p = i;
				if (a != -1) {
					if (i - a > mid) return false;
					pUsed = (i-a);
					if (mid-pUsed <= 1) {
						p = -1;
						pUsed = -1;
					}
					a = -1;
				} else {
					pUsed = -1;
				}
			} else {
				p = i;
				pUsed = -1;
			}
		}
		//cout << mid << ", " << i << ": " << p << "/" << a << "/" << pUsed << endl;
	}
	if (a > 0) return false;
	return true;
}

int main() {
	cin >> N >> line;
	int lo = 0, hi = N*2;
	while (lo < hi) {
		int mid = lo + (hi-lo)/2;
		if (ok(mid)) {
			hi = mid;
		} else {
			lo = mid+1;
		}
	}
	cout << lo << endl;
}


Comments

Submit
0 Comments
More Questions

931A - Friends Meeting
1594A - Consecutive Sum Riddle
1466A - Bovine Dilemma
454A - Little Pony and Crystal Mine
2A - Winner
1622B - Berland Music
1139B - Chocolates
1371A - Magical Sticks
1253A - Single Push
706B - Interesting drink
1265A - Beautiful String
214A - System of Equations
287A - IQ Test
1108A - Two distinct points
1064A - Make a triangle
1245C - Constanze's Machine
1005A - Tanya and Stairways
1663F - In Every Generation
1108B - Divisors of Two Integers
1175A - From Hero to Zero
1141A - Game 23
1401B - Ternary Sequence
598A - Tricky Sum
519A - A and B and Chess
725B - Food on the Plane
154B - Colliders
127B - Canvas Frames
107B - Basketball Team
245A - System Administrator
698A - Vacations